/*
题目：K个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
https://leetcode.cn/problems/reverse-nodes-in-k-group/
 */
public class ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        int i = 0;
        ListNode cur = head;
        List<ListNode> list = new ArrayList<>();//顺序表记录每一轮翻转的头结点和尾巴节点

        while (cur != null) {
            ListNode start = cur;
            while (i != k && cur != null) {
                cur = cur.next;
                i++;
            }
            ListNode end = cur;
            if (i == k) {
                list.add(reverse(start, end));//记录反转后的头节点
                list.add(start);  //反转后的尾巴节点
                i = 0;
            } else {
                cur = start;
                break;
            }
        }

        i = 1;
        for (int listSize = list.size(); i < listSize - 1; i += 2) {
            list.get(i).next = list.get(i + 1);
        }
        list.get(list.size() - 1).next = cur;

        return list.get(0);
    }

    //头插法反转
    private ListNode reverse(ListNode start, ListNode end) {
        //如果没有元素或者只有一个元素
        if (start == end && start.next == end) {
            return start;
        }
        ListNode prev = null;//记录上一个节点

        while (start != end) {
            ListNode nextNode = start.next;
            start.next = prev;
            prev = start;
            start = nextNode;
        }

        return prev; //返回翻转后的头结点
    }
}
